Backward Digit Sums    bdsum.X

Richard Mehlinger

FJ and his cows enjoy playing a mental game. They write down the
numbers from 1 to N (1 <= N <= 10) in a certain order and then sum
adjacent numbers to produce a new list with one fewer number.  They
repeat this until only a single number is left.  For example, one
instance of the game (when N=4) might go like this:

    3   1   2   4
      4   3   6
        7   9
         16

Behind FJ's back, the cows have started playing a more difficult
game, in which they try to determine the starting sequence from
only the final total and the number N.  Unfortunately, the game is
a bit above FJ's mental arithmetic capabilities.

Write a program to help FJ play the game and keep up with the cows.

PROBLEM NAME: bdsum.X

INPUT FORMAT:

* Line 1: Two space-separated integers: N and the final sum.

SAMPLE INPUT:

4 16

OUTPUT FORMAT:

* Line 1: An ordering of the integers 1..N that leads to the given
        sum.  If there are multiple solutions, choose the one that is
        lexicographically least, i.e., that puts smaller numbers
        first.

SAMPLE OUTPUT:

3 1 2 4

OUTPUT DETAILS:

There are other possible sequences, such as 3 2 1 4, but 3 1 2 4
is the lexicographically smallest.


=============================== WRITEUP ==============================
Here too is a case where brute force is actually a reasonable approach. In the worst case scenario, there are 10! = 3,628,800 combinations on the top row (and the top row, of course, completely determines all lower rows). With a worst case of 45 additions per combination then that gives us an absolute worst case of about 163,296,000 steps. This is not too much to ask a computer program to sift through, although it is too much for the ACM competition. Furthermore, the permutation function we used (which comes from itertools) generates the permutations in lexicographical order, per the requirements of the problem.

================================ CODE ================================

#!/usr/bin/python

# bdsum.X
# Richard Mehlinger and Anatole Paine

#This function generates all permutations of a given list
#in lexicographical order.
# Copied from itertools, python 2.6
def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

#returns all permutations of the list [1... N]
def findPermutations(N):
    return list(permutations(range(1, N+1)))

#Given a row, calculates the next lowest row as described in the 
#problem.
def specialSum(L):
    if len(L) <= 2:
        return sum(L)
    
    result = []
    for i in range(len(L)-1):
        result += [L[i] + L[i+1]]

    return specialSum(result)

#Searches through a list of all the permutations, and prints the
#first valid ordering it finds (which as mentioned above will be 
#the lexicographically smallest.
def findOrdering(N, target):
    orderings = findPermutations(N)

    for i in orderings:
        if specialSum(i) == target:
            out = ""
            for j in i[0:-1]:
                out += str(j) + " "
            print out + str(i[-1])
            break

def main():
    args = raw_input().split()
    N = int(args[0])
    target = int(args[1])

    findOrdering(N, target)

if __name__ == "__main__": main()